// 版权所有2009 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 通过反射进行的深度相等性测试

package reflect

import (
	"internal/bytealg"
	"unsafe"
)

// 在deepValueEqual期间，必须跟踪正在进行的检查。比较算法假设所有正在进行的
// 检查在重新计数时都为真。
// 已访问的比较存储在按访问索引的地图中。
type visit struct {
	a1  unsafe.Pointer
	a2  unsafe.Pointer
	typ Type
}

// 使用反射类型测试深度相等性。map参数跟踪已经看到的
// 比较，这允许在
// 递归类型上短路。
func deepValueEqual(v1, v2 Value, visited map[visit]bool) bool {
	if !v1.IsValid() || !v2.IsValid() {
		return v1.IsValid() == v2.IsValid()
	}
	if v1.Type() != v2.Type() {
		return false
	}

	// 我们希望避免在访问的地图中添加超出需要的内容。
	// 对于可能遇到的任何可能的引用循环，
	// hard（v1，v2）需要为循环中的至少一种类型返回true，
	// 并且获取值的内部指针是安全有效的。
	hard := func(v1, v2 Value) bool {
		switch v1.Kind() {
		case Pointer:
			if v1.typ.ptrdata == 0 {
				// go:notinheap指针不能是循环的。
				// 至少，我们目前使用的go:notinheap都有这个属性。运行时的不是循环的（我们也不在它们上面使用
				// DeepEqual），cgo生成的是
				// 所有的空结构。
				return false
			}
			fallthrough
		case Map, Slice, Interface:
			// 零指针不能是循环的。避免把它们放在地图上。
			return !v1.IsNil() && !v2.IsNil()
		}
		return false
	}

	if hard(v1, v2) {
		// 对于指针或映射值，我们需要检查flagIndir，
		// 这是通过调用指针方法来实现的。
		// 对于切片或接口，始终设置flagIndir，
		// 并且使用v.ptr就足够了。
		ptrval := func(v Value) unsafe.Pointer {
			switch v.Kind() {
			case Pointer, Map:
				return v.pointer()
			default:
				return v.ptr
			}
		}
		addr1 := ptrval(v1)
		addr2 := ptrval(v2)
		if uintptr(addr1) > uintptr(addr2) {
			// 规范化顺序，以减少访问中的条目数。
			// 假定垃圾收集器不移动。
			addr1, addr2 = addr2, addr1
		}

		// 如果已经看到参考，则短路。
		typ := v1.Type()
		v := visit{addr1, addr2, typ}
		if visited[v] {
			return true
		}

		// 以后记得。
		visited[v] = true
	}

	switch v1.Kind() {
	case Array:
		for i := 0; i < v1.Len(); i++ {
			if !deepValueEqual(v1.Index(i), v2.Index(i), visited) {
				return false
			}
		}
		return true
	case Slice:
		if v1.IsNil() != v2.IsNil() {
			return false
		}
		if v1.Len() != v2.Len() {
			return false
		}
		if v1.UnsafePointer() == v2.UnsafePointer() {
			return true
		}
		// 字节[]的特殊情况，这是常见的。
		if v1.Type().Elem().Kind() == Uint8 {
			return bytealg.Equal(v1.Bytes(), v2.Bytes())
		}
		for i := 0; i < v1.Len(); i++ {
			if !deepValueEqual(v1.Index(i), v2.Index(i), visited) {
				return false
			}
		}
		return true
	case Interface:
		if v1.IsNil() || v2.IsNil() {
			return v1.IsNil() == v2.IsNil()
		}
		return deepValueEqual(v1.Elem(), v2.Elem(), visited)
	case Pointer:
		if v1.UnsafePointer() == v2.UnsafePointer() {
			return true
		}
		return deepValueEqual(v1.Elem(), v2.Elem(), visited)
	case Struct:
		for i, n := 0, v1.NumField(); i < n; i++ {
			if !deepValueEqual(v1.Field(i), v2.Field(i), visited) {
				return false
			}
		}
		return true
	case Map:
		if v1.IsNil() != v2.IsNil() {
			return false
		}
		if v1.Len() != v2.Len() {
			return false
		}
		if v1.UnsafePointer() == v2.UnsafePointer() {
			return true
		}
		for _, k := range v1.MapKeys() {
			val1 := v1.MapIndex(k)
			val2 := v2.MapIndex(k)
			if !val1.IsValid() || !val2.IsValid() || !deepValueEqual(val1, val2, visited) {
				return false
			}
		}
		return true
	case Func:
		if v1.IsNil() && v2.IsNil() {
			return true
		}
		// 没有比这更好的了：
		return false
	case Int, Int8, Int16, Int32, Int64:
		return v1.Int() == v2.Int()
	case Uint, Uint8, Uint16, Uint32, Uint64, Uintptr:
		return v1.Uint() == v2.Uint()
	case String:
		return v1.String() == v2.String()
	case Bool:
		return v1.Bool() == v2.Bool()
	case Float32, Float64:
		return v1.Float() == v2.Float()
	case Complex64, Complex128:
		return v1.Complex() == v2.Complex()
	default:
		// 正常相等就足够了
		return valueInterface(v1, false) == valueInterface(v2, false)
	}
}

// DeepEqual报告x和y是否“深度相等”，定义如下。
// 如果下列情况之一适用，则相同类型的两个值完全相等。
// 不同类型的值永远不会完全相等。
// 
// 当数组值的对应元素深度相等时，数组值深度相等。
// 
// 如果结构值的对应字段
// 导出和未导出的字段深度相等，则结构值深度相等。
// 
// 如果两者都为零，则Func值非常相等；否则，它们就不是完全平等的。
// 
// 如果接口值具有非常相等的具体值，则它们是非常相等的。
// 
// 当以下所有条件均为真时，映射值是完全相等的：
// 它们都为零或都为非零，它们具有相同的长度，
// 并且它们要么是相同的映射对象，要么是对应的键
// （使用Go equality匹配）映射到完全相等的值。
// 
// 如果使用Go的==运算符
// 指针值相等，或者如果指针值指向非常相等的值，则指针值非常相等。
// 
// 当以下所有条件均为真时，切片值是完全相等的：
// 它们都为零或均为非零，它们具有相同的长度，
// 或者它们指向相同基础数组
// （即，&x[0]=&y[0]），或者它们对应的元素（最长）是完全相等的。
// 注意，非nil空片和nil片（例如，[]字节{}和[]字节（nil））
// 并不完全相等。
// 
// 其他值（数字、布尔值、字符串和通道）非常相等
// 如果使用Go的==运算符，它们相等。
// 
// 一般来说，DeepEqual是Go的==运算符的递归松弛。
// 然而，如果没有一些不一致性，这个想法是不可能实现的。
// 具体地说，一个值可能与自身不相等，
// 要么因为它是func类型（一般不可编译）
// 要么因为它是一个浮点NaN值（在浮点比较中不等于自身），
// 或者因为它是一个数组、结构或包含
// 这样一个值的接口。
// 另一方面，指针值始终等于它们自己，
// 即使它们指向或包含此类有问题的值
// 因为它们使用Go的==运算符比较equal，而
// 是深度相等的充分条件，无论内容如何。
// DeepEqual的定义使相同的捷径适用于切片和贴图：如果x和y是相同的切片或相同的贴图，
// 无论内容如何，它们都是深度相等的。
// 
// 当DeepEqual遍历数据值时，它可能会找到一个循环。DeepEqual比较两个指针的第二次和后续时间
// 之前比较过的值，它将这些值视为
// 相等，而不是检查它们所指向的值。
// 这确保DeepEqual终止。
func DeepEqual(x, y any) bool {
	if x == nil || y == nil {
		return x == y
	}
	v1 := ValueOf(x)
	v2 := ValueOf(y)
	if v1.Type() != v2.Type() {
		return false
	}
	return deepValueEqual(v1, v2, make(map[visit]bool))
}
